
/*
          .
         ';;;;;.
        '!;;;;;;!;`
       '!;|&#@|;;;;!:
      `;;!&####@|;;;;!:
    .;;;!&@$$%|!;;;;;;!'.`:::::'.
     '!;;;;;;;;!$@###&|;;|%!;!$|;;;;|&&;.
     :!;;;;!$@&%|;;;;;;;;;|!::!!:::;!$%;!$%`    '!%&#########@$!:.
     ;!;;!!;;;;;|$$&@##$;;;::'''''::;;;;|&|%@$|;;;;;;;;;;;;;;;;!$;
     ;|;;;;;;;;;;;;;;;;;;!%@#####&!:::;!;;;;;;;;;;!&####@%!;;;;$%`
    `!!;;;;;;;;;;!|%%|!!;::;;|@##%|$|;;;;;;;;;;;;!|%$#####%;;;%&;
    :@###&!:;;!!||%%%%%|!;;;;;||;;;;||!$&&@@%;;;;;;;|$$##$;;;%@|
    ;|::;;;;;;;;;;;;|&&$|;;!$@&$!;;;;!;;;;;;;;;;;;;;;;!%|;;;%@%.
   `!!;;;;;;;!!!!;;;;;$@@@&&&&&@$!;!%|;;;;!||!;;;;;!|%%%!;;%@|.
%&&$!;;;;;!;;;;;;;;;;;|$&&&&&&&&&@@%!%%;!||!;;;;;;;;;;;;;$##!
!%;;;;;;!%!:;;;;;;;;;;!$&&&&&&&&&&@##&%|||;;;!!||!;;;;;;;$&:
':|@###%;:;;;;;;;;;;;;!%$&&&&&&@@$!;;;;;;;!!!;;;;;%&!;;|&%.
 !@|;;;;;;;;;;;;;;;;;;|%|$&&$%&&|;;;;;;;;;;;;!;;;;;!&@@&'
  .:%#&!;;;;;;;;;;;;;;!%|$$%%&@%;;;;;;;;;;;;;;;;;;;!&@:
  .%$;;;;;;;;;;;;;;;;;;|$$$$@&|;;;;;;;;;;;;;;;;;;;;%@%.
    !&!;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;|@#;
     `%$!;;;;;;;;;;;$@|;;;;;;;;;;;;;;;;;;;;;;;;!%$@#@|.
       .|@%!;;;;;;;;;!$&%||;;;;;;;;;;;;;;;;;!%$$$$$@#|.
           ;&$!;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;%#####|.
           |##$|!;;;;;;::'':;;;;;;;;;;;;;!%$$$@#@;
          ;@&|;;;;;;;::'''''':;;;;;;;|$&@###@|`
        .%##@|;;;;:::''''''''''::;!%&##$'
      `$##@$$@@&|!!;;;:'''''::::;;;;;|&#%.
    ;&@##&$%!;;;;;;::''''''''::;!|%$@#@&@@:
     .%@&$$|;;;;;;;;;;:'''':''''::;;;%@#@@#%.
    :@##@###@$$$$$|;;:'''':;;!!;;;;;;!$#@@#$;`
     `%@$$|;;;;;;;;:'''''''::;;;;|%$$|!!&###&'
     |##&%!;;;;;::''''''''''''::;;;;;;;!$@&:`!'
    :;!@$|;;;;;;;::''''''''''':;;;;;;;;!%&@$:                !@#$'
      |##@@&%;;;;;::''''''''':;;;;;;;!%&@#@$%:            '%%!%&;
      |&%!;;;;;;;%$!:''''''':|%!;;;;;;;;|&@%||`         '%$|!%&;
      |@%!;;!!;;;||;:'''''':;%$!;;;;!%%%&#&%$&:        .|%;:!&%`
      !@&%;;;;;;;||;;;:''::;;%$!;;;;;;;|&@%;!$;       `%&%!!$&:
      '$$|;!!!!;;||;;;;;;;;;;%%;;;;;;;|@@|!$##;      !$!;:!$&:
       |#&|;;;;;;!||;;;;;;;;!%|;;;;!$##$;;;;|%'   `%$|%%;|&$'
        |&%!;;;;;;|%;;;;;;;;$$;;;;;;|&&|!|%&&;  .:%&$!;;;:!$@!
        `%#&%!!;;;;||;;;;;!$&|;;;!%%%@&!;;;!!;;;|%!;;%@$!%@!
        !&!;;;;;;;;;||;;%&!;;;;;;;;;%@&!;;!&$;;;|&%;;;%@%`
       '%|;;;;;;;;!!|$|%&%;;;;;;;;;;|&#&|!!||!!|%$@@|'
       .!%%&%'`|$;     :|$#%|@#&;%#%.
*/
#include <windows.h>
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <experimental/string_view>
#define lbt(x) (x&(-x))
#define mes(a,b) memset(a,b,sizeof(a))
#define IOS ios::sync_with_stdio(false)
#define UPCASE( c ) ( ((c) >= 'c' && (c) <= 'z') ? ((c) - 0x20) : (c) )
#define FullWidth GetSystemMetrics(SM_CXSCREEN)
#define FullHeight GetSystemMetrics(SM_CYSCREEN)

#define pb push_back
#define mkp make_pair
using namespace std;
using namespace __gnu_pbds;
using pii=pair<int,int>;
using Balanced_Tree=tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>;
Balanced_Tree seq;

const int N=1e6+28;
const double Eps=1e-7 ;
typedef long long int ll;

const long long mod = 1e9+7 ;
inline ll pow_mod (ll a,ll b) {ll res=1;a%=mod; if(b<0) return -1; for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
inline ll fas_mul (ll a,ll b) { return ( (a*b-(ll)(((long double)a*b+0.5)/mod)*mod)%mod+mod)%mod ; }

namespace io {

    #define in(a) a=read()
    #define out(a) write(a)
    #define outn(a) out(a),putchar('\n')

    #define I_int __int128
    inline I_int read() {
        I_int x = 0 , f = 1 ; char c = getchar() ;
        while( c < '0' || c > '9' ) { if( c == '-' ) f = -1 ; c = getchar() ; }
        while( c >= '0' && c <= '9' ) { x = x * 10 + c - '0' ; c = getchar() ; }
        return x * f ;
    }
    char F[ 200 ] ;
    inline void write( I_int x ) {
        if( x == 0 ) { putchar( '0' ) ; return ; }
        I_int tmp = x > 0 ? x : -x ;
        if( x < 0 ) putchar( '-' ) ;
        int cnt = 0 ;
        while( tmp > 0 ) {
            F[ cnt ++ ] = tmp % 10 + '0' ;
            tmp /= 10 ;
        }
        while( cnt > 0 ) putchar ( F[ -- cnt ] ) ;
    }
    #undef I_int

}using namespace io ;


int Height=650,
    Width=650 ;
const int N=1e6+28 ; 
const double Eps = 1e-7 ;

namespace FFT
{
    const double pi=acos(-1);
    struct Complex{
	   double x,y;
	   Complex(double a=0,double b=0){ x=a,y=b; } ;
    };
    Complex operator + ( Complex a,Complex b){return Complex(a.x+b.x,a.y+b.y);}
    Complex operator - (Complex a,Complex b){return Complex(a.x-b.x,a.y-b.y);}
    Complex operator * (Complex a,Complex b){return Complex(a.x*b.x-a.y*b.y,a.y*b.x+a.x*b.y);}
    Complex operator * (Complex a,double b){return Complex(a.x*b,a.y*b);}
    Complex operator * ( double a,Complex b){return Complex(b.x*a,b.y*a);}
    int rota[N] ;
    int pre(int n){
	   int cnt=1 ;
	   int high=0 ;
	   while(cnt<n)
            cnt<<=1 ,
            high++ ;
	   for( int i=0;i<cnt;i++ )
	       rota[i]=(rota[i>>1]>>1)|((i&1)<<(high-1));
	   return cnt ;
    }
    int lim ;
    void fft(int n,Complex *buf,int fft){
	   lim=pre(n);
	   for(int i=0;i<lim;i++)if(i<rota[i])swap(buf[i],buf[rota[i]]);
	   for(int len=2;len<=lim;len<<=1)
       {
	        Complex wn = Complex(cos(fft*2*pi/len),sin(fft*2*pi/len)) ;
	        for(int s=0;s<lim;s+=len)
            {
		        Complex w=Complex(1,0);
		        for(int k=s;k<s+len/2;k++,w=w*wn)
                {
                    Complex x,y;
                    x=buf[k],y=w*buf[k+len/2];
                    buf[k]=x+y;
                    buf[k+len/2]=x-y;
		        }
	        }  
	   }
    }
    void CalcPos(double n,Complex *buf,Complex *pos){
        for(int k=0;k<lim;k++)
        {
           pos[k]=buf[k]*Complex(cos(2*pi*k*n/lim),sin(2*pi*k*n/lim));
           pos[k].x/=lim,pos[k].y/=lim;
        }
    }
    double Length(Complex X){
	   return sqrt(X.x*X.x+X.y*X.y);
    }
}
using namespace FFT;
LRESULT CALLBACK WndProc(HWND hwnd, UINT Message, WPARAM wParam, LPARAM lParam);
void Paint(HWND hwnd);
void Init(HWND hwnd);
void Copy(char *buf);
void DrawTransBitmap(HDC hdcDest,int nXOriginDest,int nYOriginDest,int nWidthDest,int nHeightDest,HDC hdcSrc,int nXOriginSrc,int nYOriginSrc,COLORREF crTransparent);
int tot,getStart,Stop;
double step;
Complex pos[N],point[N];

/**
 * @brief      ShowDrawing
 *
 * @param[in]  hInstance      hInstance
 * @param[in]  hPrevInstance  hPrevInastance
 * @param[in]  lpCmdLine      lpCmdLine
 * @param[in]  nCmdShow       nCmdShow
 *
 * @return     massege.param
 */
int WINAPI WinMain(HINSTANCE hInstance, HINSTANCE hPrevInstance, LPSTR lpCmdLine, int nCmdShow) {
    WNDCLASSEX wc;
    HWND hwnd;
    MSG msg;
    memset(&wc,0,sizeof(wc));
    wc.cbSize		 = sizeof(WNDCLASSEX);
    wc.lpfnWndProc	 = WndProc;
    wc.hInstance	 = hInstance;
    wc.hCursor		 = LoadCursor(NULL, IDC_ARROW);
    wc.hbrBackground = (HBRUSH)(COLOR_WINDOW+1);
    wc.lpszClassName = "WindowClass";
    wc.hIcon=(HICON)LoadImage(GetModuleHandle(0),"lll.ico",IMAGE_ICON,128,128,LR_LOADFROMFILE|LR_CREATEDIBSECTION);
    wc.hIconSm=(HICON)LoadImage(GetModuleHandle(0),"lll.ico",IMAGE_ICON,128,128,LR_LOADFROMFILE|LR_CREATEDIBSECTION);
    if(!RegisterClassEx(&wc)) {MessageBox(NULL, "Window Registration Failed!","Error!",MB_ICONEXCLAMATION|MB_OK);return 0;}
    hwnd=CreateWindowEx(
			WS_EX_CLIENTEDGE,
			"WindowClass","Fourier Draw",
			WS_VISIBLE|WS_OVERLAPPEDWINDOW,
			(FullWidth-Width-20)/2,(FullHeight-Height-40)/2,
			Width+21,Height+45,
			NULL,
			NULL,
			hInstance,
			NULL
			);
    if(hwnd==NULL)
    {
        MessageBox(
            NULL,
            "Window Creation Failed!",
            "Error!",
            MB_ICONEXCLAMATION|MB_OK
            );
        return 0;
    }
    Init( hwnd );
    double start=clock();
    int wait=0;
    while( msg.message!=WM_QUIT )
    {
	   if( PeekMessage( &msg,NULL,0,0,PM_REMOVE ) )
       {
	       TranslateMessage(&msg);
	       DispatchMessage(&msg);
	   }else{
	       double wait=0.1;
	       if( getStart&&tot>=10000 )
                wait=0.01;
	       if(clock()>=start+wait*CLOCKS_PER_SEC)
                start+=wait*CLOCKS_PER_SEC;
	       else continue;
	       if(getStart&&Stop==0)
           {
		      if( step>1.0*tot-(Eps))step=0;
		      Paint(hwnd) ;
		      step+=1 ;
	       }else{
		      Paint(hwnd) ;
	       }
	   }
    }
    return msg.wParam ;
}
//Last Updated by [Ling] --[2019-11-13 21:19:06] 

HDC WinMap,dWinMap,ddm;
HBITMAP dbm,ddbm;
HBRUSH black,red,green,blue,white,grey,dark,Indirect;
HPEN Black,White,Green,Red,Blue,Grey;

//  Function:  Init
//  Parameter: HWND
//  Re_value:  void
//  Init the window graph _Ling
void Init(HWND hwnd){
    srand(time(0));
    //SetWindowLong(hwnd,GWL_STYLE,GetWindowLong(hwnd,GWL_STYLE)&(~WS_MAXIMIZEBOX&~WS_THICKFRAME));
    black = CreateSolidBrush(RGB(0,0,0));
    grey  = CreateSolidBrush(RGB(100,100,100));
    red   = CreateSolidBrush(RGB(255,0,0));
    green = CreateSolidBrush(RGB(0,255,0));
    blue  = CreateSolidBrush(RGB(0,0,255));
    white = CreateSolidBrush(RGB(255,255,255));
    Black = CreatePen(PS_SOLID,0,RGB(0,0,0));
    Grey  = CreatePen(PS_SOLID,0,RGB(100,100,100));
    White = CreatePen(PS_SOLID,0,RGB(255,255,255));
    Green = CreatePen(PS_SOLID,2,RGB(0,255,0));
    Red   = CreatePen(PS_SOLID,0,RGB(255,0,0));
    Blue  = CreatePen(PS_SOLID,0,RGB(0,0,255));
    LOGBRUSH logbr;
    memset(&logbr,0,sizeof(LOGBRUSH));   
    logbr.lbColor = RGB(255,255,255);
    logbr.lbStyle = BS_NULL;
    Indirect      = CreateBrushIndirect(&logbr);
    WinMap        =GetDC(hwnd);
    dWinMap       =CreateCompatibleDC(WinMap);
    dbm           =CreateCompatibleBitmap(WinMap,FullWidth,FullHeight);
    SelectObject(dWinMap,dbm);
    SetBkMode(dWinMap,TRANSPARENT);
    ddm           =CreateCompatibleDC(dWinMap);
    ddbm          =CreateCompatibleBitmap(dWinMap,FullWidth,FullHeight);
    SelectObject(ddm,ddbm);
    SelectObject(ddm,Green);
    SetBkMode(ddm,TRANSPARENT);
    freopen("data.in","r",stdin);
    int tmp;
    if( ~scanf("%d",&tmp) ){
       tot=tmp;
       for( int i=0 ; i<tot ; i++ )
           if(scanf("%lf%lf",&point[i].x,&point[i].y)==EOF)break;
   }
   freopen("CON","r",stdin);
}

char s[256];
int cnt , 
    Show ,
    Hide ;
Complex draw[N],
        vec[N] ;

//  Function:  Paint
//  Parameter: HWND
//  Re_value:  void

void Paint( HWND hwnd )
{
    SelectObject(dWinMap,white);
    SelectObject(dWinMap,White);
    Rectangle(dWinMap,0,0,Width,Height);
    SelectObject(dWinMap,black);
    SelectObject(dWinMap,Black);
    if(getStart==0||Show){
	   for( int i=0 ; i<tot ; ++i )
	       Rectangle(dWinMap,(int)point[i].x-2,(int)point[i].y-2,(int)point[i].x+2,(int)point[i].y+2);
    }
    if( getStart ){
        SelectObject(dWinMap,Indirect);
        if(step<1e-7){
            cnt=0;
            SelectObject(ddm,white);
            SelectObject(ddm,White);
            Rectangle(ddm,0,0,FullWidth,FullHeight);
            SelectObject(ddm,Green);
        }
    	CalcPos(step,pos,vec);
    	draw[++cnt]=Complex(0,0);
    	MoveToEx(dWinMap,0,0,NULL);

    	for( int i=0 ; i<lim ; ++i )
        {
            int len   =(int)Length(vec[i]);
            SelectObject(dWinMap,Red);
            if(Hide   ==0&&len)Ellipse(dWinMap,(int)draw[cnt].x-len,(int)draw[cnt].y-len,(int)draw[cnt].x+len,(int)draw[cnt].y+len);
            draw[cnt] =draw[cnt]+vec[i];
            SelectObject(dWinMap,Blue);
            if(!Hide)LineTo(dWinMap,(int)draw[cnt].x,(int)draw[cnt].y);
    	}
    	if(cnt>1){
    	   MoveToEx(ddm,(int)draw[cnt-1].x,(int)draw[cnt-1].y,NULL);
    	   LineTo(ddm,(int)draw[cnt].x,(int)draw[cnt].y);
    	}
    }
    if(getStart)DrawTransBitmap(dWinMap,0,0,Width,Height,ddm,0,0,RGB(255,255,255));
    BitBlt(WinMap,0,0,Width,Height,dWinMap,0,0,SRCCOPY);
}

void Copy(char *buf)
{
    int len=strlen(buf)+1;
    if(OpenClipboard(NULL)){
    	HGLOBAL hmem=GlobalAlloc(GHND,len);
        char *pmem=(char*)GlobalLock(hmem);
    	EmptyClipboard();
    	memcpy(pmem,buf,len);
    	SetClipboardData(CF_TEXT,hmem);
    	CloseClipboard();
    	GlobalFree(hmem);
    }
}

//  Function:  DrawBMP
//  Parameter: key::BMP
//  Re_value:  void
//  You can find the path of bmp about how to draw _LING

void DrawTransBitmap(HDC hdcDest,int nXOriginDest,int nYOriginDest,int nWidthDest,int nHeightDest,HDC hdcSrc,int nXOriginSrc,int nYOriginSrc,COLORREF crTransparent)
{
    HBITMAP hOldImageBMP, hImageBMP = CreateCompatibleBitmap(hdcDest, nWidthDest, nHeightDest);   
    HBITMAP hOldMaskBMP, hMaskBMP   = CreateBitmap(nWidthDest, nHeightDest, 1, 1, NULL);  
    HDC hImageDC                    = CreateCompatibleDC(hdcDest); 
    HDC hMaskDC                     = CreateCompatibleDC(hdcDest);
    hOldImageBMP                    = (HBITMAP)SelectObject(hImageDC, hImageBMP);
    hOldMaskBMP                     = (HBITMAP)SelectObject(hMaskDC, hMaskBMP);
    BitBlt(hImageDC, 0, 0, nWidthDest, nHeightDest, hdcSrc, nXOriginSrc, nYOriginSrc, SRCCOPY);
    SetBkColor(hImageDC, crTransparent);
    BitBlt(hMaskDC, 0, 0, nWidthDest, nHeightDest, hImageDC, 0, 0, SRCCOPY);
    BitBlt(hdcDest, nXOriginDest, nYOriginDest, nWidthDest, nHeightDest, hImageDC, 0, 0, SRCINVERT);
    BitBlt(hdcDest, nXOriginDest, nYOriginDest, nWidthDest, nHeightDest, hMaskDC, 0, 0, SRCAND);
    BitBlt(hdcDest, nXOriginDest, nYOriginDest, nWidthDest, nHeightDest, hImageDC, 0, 0, SRCINVERT);
    SelectObject(hImageDC, hOldImageBMP);
    DeleteDC(hImageDC);
    SelectObject(hMaskDC, hOldMaskBMP);
    DeleteDC(hMaskDC);
    DeleteObject(hImageBMP);
    DeleteObject(hMaskBMP);
}
LRESULT CALLBACK WndProc(HWND hwnd,UINT Message,WPARAM wParam,LPARAM lParam)
{
    switch(Message)
    {
        case WM_DESTROY:
        {   
            PostQuitMessage(0) ;
            break ;
        } 
        case WM_LBUTTONDOWN:
        {
            double x=(double)LOWORD(lParam),y=(double)HIWORD(lParam);
            point[tot++]=Complex(x,y);
            point[tot]=Complex(0,0);
            break;
        }
        case WM_KEYDOWN:
        {
	       switch(wParam)
           {
                case VK_ESCAPE:
                {
                   getStart=tot=0;
                   memset(point,0,sizeof(point));
                   break;
                }
                case 'Z':
                {
                   if(tot)tot--;
                   break;
                }
                case 'X':
                {
                   if(point[tot].x>1e-7)tot++;
                   break;
                }
                case VK_F5:
                {
                   if(getStart==0)
                   {
                        getStart=1;
                        Stop=0,step=0,cnt=0;
                        int lim=pre(tot);
                        memcpy(pos,point,lim*sizeof(Complex));
                        fft(tot,pos,-1);
                   }else{
                        getStart=0;
                        SelectObject(ddm,white);
                        SelectObject(ddm,White);
                        Rectangle(ddm,0,0,Width,Height);
                   }
                    break;
                }
                case VK_SPACE:
                {
                    Stop=1-Stop;
                    break;
                }
                case VK_F1:
                {
                   Show=1-Show;
                   break;
                }
                case VK_F2:
                {
                   Hide=1-Hide;
                   break;
                }
	       }
	       break;
        }
        case WM_PAINT:
        {
           RECT rct;
           GetWindowRect(hwnd,&rct);
           Width  =rct.right-rct.left;
           Height =rct.bottom-rct.top;
        }
        default:
            return DefWindowProc(hwnd,Message,wParam,lParam);
    }
    return 0;
}
/*

*/
